package leetcode;
import java.util.*;
/**
 * 47.全排列Ⅱ
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 *
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],[1,2,1],[2,1,1]]
 *
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 */
public class Num_47 {
    List<Integer> inner = new ArrayList<>();
    List<List<Integer>> outter = new ArrayList<>();
    Set<Integer> set = new HashSet<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        dfs(nums);
        return outter;
    }

    private void dfs(int[] nums) {
        //边界条件
        if(inner.size() == nums.length){
            outter.add(new ArrayList<>(inner));
            return;
        }

        //这里也需要设置一个去重器，去除该层的重复元素
        Set<Integer> set2 = new HashSet<>();
        //每层从0开始
        for (int i = 0; i < nums.length; i++) {
            //set集合添加num的下标位置，因为有重复元素，但是下标不可能重复
            if(!set2.contains(nums[i]) && !set.contains(i)){
                //此时，三个集合中都需要添加对应的元素
                set.add(i);
                set2.add(nums[i]);
                inner.add(nums[i]);
                //递归
                dfs(nums);
                //回溯删除
                inner.remove(inner.size() - 1);
                set.remove(i);
                //此时不需要删除set2中的元素，因为set2只是检验同一层是否遍历过该值的元素
            }
        }
    }
}
